1. Field of Invention
The present invention relates generally to methods and apparatus for bit-serial processing operands in a computational-based device, to produce the value of arithmetic expressions. More particularly, the present invention relates to a method and apparatus for bit-serial processing the operands A, B and C in a computational device, to produce the value of the arithmetic expression S=(A.times.B)+C where each operand A, B and C are expressed as a sequence of digits, with the most significant digit of each operand entering the computational device first, and the most significant digit of the arithmetic expression S=(A.times.B)+C being produced first.
2. Description of the Prior Art
There is a great need to compute basic arithmetic expressions such as (A.times.B)+C, where operands A, B and C are digitally represented as a sequence of digits of binary value. The reason for this need is quite simple. Most computational functions and digital signal processing techniques (e.g. digital finite impulse response (FIR) filters, discrete Fourier transforms (DFT), discrete Walsh transforms (DWT), discrete Hartley transforms (DHT), matrix-vector multiplication and the like), are realizable as a particular combination of arithmetic units (i.e. "building blocks"), each carrying out the arithmetic function (A.times.B)+C.
In this regard, "computational efficiency" and speed with which the arithmetic expression (A.times.B)+C can be computed in a computational-based device, is most important, especially in demanding signal processing applications.
In methods and apparatus involving the simultaneous processing of a set of digits (i.e. a word), hereinafter referred to as "word-parallel processing", the arithmetic expression (A.times.B)+C can only be computed upon the simultaneous availability of all of the digits of the operands A, B and C. Consequently, such methods and apparatus suffer from several significant shortcomings and drawbacks. In particular, evaluation of the arithmetic expression (A.times.B)+C cannot be undertaken until all of the digits of the operands are available. As a result, such word-parallel processing methods and apparatus are undesirable for particularly demanding real-time signal processing applications. Also, additional digit storage requirements and processing time are needed to implement such word-parallel processing techniques.
In response to the shortcomings and drawbacks of the above-type "word-parallel" processing methods and apparatus, several "bit-serial" processing methods and arithmetic processors have been proposed.
One particular "bit-serial" processing technique involves computation of the arithmetic expression (A.times.B)+C by providing one digit of each operand A, B and C at a time, to produce in a digit-by-digit manner, the value of (A.times.B)+C starting from the least significant digit (LSD). Such a method, however, has several significant shortcomings and drawbacks. In particular, the data word length of the result (A X B)+C is doubled whenever a multiplication operation is performed. Thus, since the output therefrom must be truncated to a fixed word length, the computation time used to produce the second half of the product is wasted in a computational sense. In addition, such a method of bit-serial processing commences from the least significant digit (LSD) of the operand, which normally is not available first from the analog-to-digital converter employed in sampled-signal processing applications. Consequently, additional storage and processing time are needed to implement such bit-serial processing methods, commencing from the least significant digit (or bit).
An alternative bit-serial processing method and arithmetic processor is disclosed in a paper entitled "Design and VLSI Implementation of an On-Line Algorithm" by D. Ercegovac et al., published in Vol. 698 Real Time Signal Processing IX (1986) of The Society of Photooptical Instrumentation Engineers (SPIE). Therein, Ercegovac et al. propose an "on-line", bit-serial method and arithmetic processor for computing the arithmetic expression (A.multidot.X)+B, which is mathematically equivalent to the above-described expression (A.times.B)+C. In Ercegovac et al.'s bit-serial processing method and arithmetic processor, operands A and X are available "on-line" and are expressed in a radix-2 signed-digit format with the most significant digit provided to the arithmetic processor first, whereas operand B is available "off-line" (word-parallel) in a two's complement format.
In "on-line" computational processes of the type disclosed in Ercegovac et al.'s above-referenced paper, the operands A and X, as well as the results of any arithmetic operation involving the same, flow through the arithmetic processor in a digit-by-digit manner, starting with the most significant digit. In order to generate the j-th digit of the result (e.g. (A.multidot.X)+B), j+.delta. digits of the corresponding operands A and X are required, where .delta., the on-line delay, is usually a small integer. As soon as .delta. input digits are available, then successive operations are executed in an overlapped manner in such bit-serial arithmetic processors.
In order that the arithmetic can be carried out from left-to-right (contrary to conventional right-to-left arithmetic methods) and thus be capable of computing the value of the arithmetic expression (A.multidot.X)+B starting from the most significant digit, a redundant binary number system is employed in the Ercegovac et al. bit-serial processing method and arithmetic processor. While the format of output data digits must be in the signed-digit form, and consequently the input format into each arithmetic processor of Ercegovac et al. must subsume the signed-digit form, all internal arithmetic operations are executed in regular binary representation (e.g. two's complement form). Thus, input operands A, X and B must be converted "on-the-fly" from signed-digit form into two's complement form.
The on-line method and arithmetic processor of Ercegovac et al. has several advantages over all bit-parallel and most other bit-serial types of processing, namely:
(i) computation of the expression (A.multidot.X)+B can commence when the most significant digit of a signal sample is available from the analog-to-digital converter, thereby improving the arithmetic processor throughput by a factor of N, where N is the number of digits from the analog-to-digital converter; PA1 (ii) truncation of the output of the processor's digital multiplier occurs at a fixed time interval, in order to maintain a constant word length, thereby improving the processor throughput by a factor of two (2) since the second half or least significant word of the product (A.multidot.X) is not performed; and PA1 (iii) commencement of the second stage of computation in a computational-based device (configured from such an arithmetic processor), can begin whenever the most significant digit of the first output therefrom is available, and commencement of a third stage of computation in such a computational-based device, can begin as soon as the most significant digit of the second stage output is available, and so on for subsequent stages. Thus, by overlapping the computation of successive digits of operands, a significant improvement in the overall processor can be achieved.
However, the method and arithmetic processor of Ercegovac et al. suffer from several significant shortcomings and drawbacks.
In the Ercegovac et al. arithmetic processor, only two operands (i.e. A and X) can be "on-line", and the third operand B must be present in "off-line" (i.e. bit-parallel or digit-parallel) form. Consequently, the input-output requirements of any arithmetic processor realizing the Ercegovac et al. method are substantially large and for the most part are not minimizable.
Also, the Ercegovac et al. arithmetic processor when employed in constructing digital (FIR) filters, results in a digital filter characterized by relatively slow data throughput because all of the digits of operand C in the expression (A.times.B)+C must be simultaneously available to produce the resulting arithmetic expression.
In view, therefore, of the shortcomings and drawbacks of prior art methods and apparatus for arithmetic processing, there is a clear need in data processing arts for a method and apparatus for bit-serial processing operands available in an on-line fashion, so as to provide in computationally efficient and high-speed manner, the value of the arithmetic expression (A X B)+C, starting from the most significant digit first.